package com.algrithom.stack;

/**
 * 整数划分问题 整数拆分问题
 *
 * @author think
 * @version 1.0.0
 * @since 2019/12/31
 */
public class IntegerDiv {
    
    public static void main(String[] args){
        System.out.println(integerDiv(5,5));
        System.out.println(integerSplit(10));
        System.out.println(integerBreak(10));
    }
    
    /**
     * 整数划分为子整数的情况下的个数
     *
     * @param n 输入
     * @param m 最大子整数
     * @return 情况总和
     */
    private static int integerDiv(int n,int m){
        if (n < 1 || m < 1) {
            return 0;
        }
        if (n == 1 || m == 1) {
            return 1;
        }
        if (n < m) {
            return integerDiv(n,n);
        }
        if (n == m) {
            return integerDiv(n,m - 1) + 1;
        }
        return integerDiv(n,m - 1) + integerDiv(n - m,m);
    }
    
    /**
     * 整数拆分 动态规划解法
     *
     * @param n 输入的正整数
     * @return 拆分的数据的最大乘积
     */
    private static int integerSplit(int n){
        int[] temp = new int[n + 1];
        temp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                temp[i] = Math.max(temp[i],Math.max(temp[j],j) * (i - j));
            }
        }
        return temp[n];
    }
    
    /**
     * 整数拆分 贪心算法解法
     *
     * @param n 输入
     * @return 最大乘积
     */
    private static int integerBreak(int n){
        if (n == 2) {
            return 1;
        }
        if (n == 3) {
            return 2;
        }
        if (n == 4) {
            return 4;
        }
        int a = n / 3;
        int b = n % 3;
        if (b == 0) {
            return (int)Math.pow(3,a);
        }
        if (b == 1) {
            return (int)Math.pow(3,a - 1) * 4;
        }
        return (int)Math.pow(3,a) * 2;
    }
}
